"""
归并排序
"""


def merge_sort(items: list) -> list:
  if len(items) > 1:
    middle = len(items) // 2
    left, right = items[:middle], items[middle:]

    merge_sort(left)
    merge_sort(right)

    i, j, k = 0, 0, 0
    while i < len(left) and j < len(right):
      if left[i] < right[j]:
        items[k] = left[i]
        i += 1
      else:
        items[k] = right[j]
        j += 1
      k += 1

    while i < len(left):
      items[k] = left[i]
      i += 1
      k += 1

    while j < len(right):
      items[k] = right[j]
      j += 1
      k += 1
  return items
